package cn.lishiyuan.algorithm.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 归并排序
 * <br>
 * 归并排序的思路是，将集合分成左右两部分，左右两部分都是已经排好序的，然后将这两部分合集进行合并。
 * <br>
 * 使用递归与分治思想，将问题规模逐步减小。小问题解决了，原问题也就解决了。
 *
 */
public class MergeSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {
        mergeSort(data, 0, data.size() - 1);
        return data;
    }

    private <T extends Comparable<T>> void mergeSort(List<T> data, int left, int right) {
        // 只有一个元素
        if(right == left){
            return;
        }
        // 防止int溢出
        int mid = left + (right - left) / 2;
        mergeSort(data, left, mid);
        mergeSort(data, mid + 1, right);
        merge(data, left, right, mid);


    }

    private static <T extends Comparable<T>> void merge(List<T> data, int left, int right, int mid) {
        // 合并数据
        int i = left;
        int j = mid + 1;
        int length = (right - left) +1;
        List<T> l = new ArrayList<>(length);
        for(int k = 0; k < length; k++){
            // 如果左边已经完全到达末尾则将右边放进去就行
            if(i > mid){
                l.add(data.get(j));
                j++;
                continue;
            }
            // 如果右边已经完全到达末尾则将左边放进去就行
            if(j > right){
                l.add(data.get(i));
                i++;
                continue;
            }

            // 将小的那个放入
            if (data.get(i).compareTo(data.get(j)) <= 0) {
                l.add(data.get(i));
                i++;
            }else {
                l.add(data.get(j));
                j++;
            }
        }
        // 将有序的元素放入原合集
        for (int k = 0; k < l.size(); k++) {
            data.set((left +k), l.get(k));
        }
    }

    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {
        mergeSort(data, 0, data.length - 1);
        return data;
    }

    private <T extends Comparable<T>> void mergeSort(T[] data, int left, int right) {
        // 只有一个元素
        if(right == left){
            return;
        }
        // 防止int溢出
        int mid = left + (right - left) / 2;
        mergeSort(data, left, mid);
        mergeSort(data, mid + 1, right);
        merge(data, left, right, mid);
    }

    private <T extends Comparable<T>> void merge(T[] data, int left, int right, int mid) {
        // 合并数据
        int i = left;
        int j = mid + 1;
        Object[] l = new Object[(right - left) + 1];
        for(int k = 0; k < l.length; k++){
            // 如果左边已经完全到达末尾则将右边放进去就行
            if(i > mid){
                l[k] = data[j];
                j++;
                continue;
            }
            // 如果右边已经完全到达末尾则将左边放进去就行
            if(j > right){
                l[k] = data[i];
                i++;
                continue;
            }
            // 将小的那个放入
            if (data[i].compareTo(data[j]) <= 0) {
                l[k] = data[i];
                i++;
            }else {
                l[k] = data[j];
                j++;
            }
        }

        // 将有序的元素放入原合集
        for (int k = 0; k < l.length; k++) {
            data[ left +k ] = (T) l[k];
        }
    }

}
